// 版权所有2009年围棋作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// Package flate实现DEFLATE压缩数据格式，如中所述
// RFC 1951。gzip和zlib包实现了对基于DEFLATE的文件的访问
// 格式。
package flate

import (
	"bufio"
	"io"
	"math/bits"
	"strconv"
	"sync"
)

const (
	maxCodeLen = 16 // 哈夫曼码的最大长度
	// 接下来的三个数字来自RFC第3.2.7节，带有
	// 第3.2.5节中的附加但书，其中暗示距离代码
	// 30和31不应出现在压缩数据中。
	maxNumLit  = 286
	maxNumDist = 30
	numCodes   = 19 // 哈夫曼元代码中的代码数
)

// 仅在首次使用时初始化fixedHuffmanDecoder一次。
var fixedOnce sync.Once
var fixedHuffmanDecoder huffmanDecoder

// CorruptInputError报告给定偏移量处存在损坏的输入。
type CorruptInputError int64

func (e CorruptInputError) Error() string {
	return "flate: corrupt input before offset " + strconv.FormatInt(int64(e), 10)
}

// 内部错误报告扁平代码本身的错误。
type InternalError string

func (e InternalError) Error() string { return "flate: internal error: " + string(e) }

// ReadError报告读取输入时遇到的错误。
// None
// 已弃用：不再返回。
type ReadError struct {
	Offset int64 // 发生错误的字节偏移量
	Err    error // 底层读取返回错误
}

func (e *ReadError) Error() string {
	return "flate: read error at offset " + strconv.FormatInt(e.Offset, 10) + ": " + e.Err.Error()
}

// WriteError报告写入输出时遇到的错误。
// None
// 已弃用：不再返回。
type WriteError struct {
	Offset int64 // 发生错误的字节偏移量
	Err    error // 基础写操作返回错误
}

func (e *WriteError) Error() string {
	return "flate: write error at offset " + strconv.FormatInt(e.Offset, 10) + ": " + e.Err.Error()
}

// 重置器重置NewReader或NewReaderDict返回的ReadCloser
// 切换到新的底层读取器。这允许重新使用ReadCloser
// 而不是分配一个新的。
type Resetter interface {
	// 重置将丢弃任何缓冲数据，并将重置器重置为
	// 使用给定的读取器新初始化。
	Reset(r io.Reader, dict []byte) error
}

// 解码哈夫曼表的数据结构基于
// 兹利布。有一个固定位宽（huffbits）的查找表，
// 对于小于表格宽度的代码，有多个条目
// （每个尾随位组合具有相同的值）。代码
// 大于表格宽度时，表格包含指向溢出的链接
// 桌子链接表中每个条目的宽度是最大代码
// 大小减去块宽度。
// None
// 请注意，即使没有所有位，也可以在表中进行查找
// 填满。因为额外的位是零，而泄气的哈夫曼码
// 具有短代码先于长代码的特性
// 结果中的位长度估计值是实际值的下限
// 位数。
// None
// 见下文：
// https:

// chunk&15是位数
// chunk>>4是值，包括表链接

const (
	huffmanChunkBits  = 9
	huffmanNumChunks  = 1 << huffmanChunkBits
	huffmanCountMask  = 15
	huffmanValueShift = 4
)

type huffmanDecoder struct {
	min      int                      // 最小代码长度
	chunks   [huffmanNumChunks]uint32 // 如上所述的块
	links    [][]uint32               // 溢出链接
	linkMask uint32                   // 屏蔽链接表的宽度
}

// 从代码长度数组初始化哈夫曼解码表。
// 在此函数之后，h保证被初始化为一个完整的
// 树（即，既不超额认购也不不足认购）。例外情况是
// 树只有一个长度为1的符号的退化情况。空的
// 树木是允许的。
func (h *huffmanDecoder) init(lengths []int) bool {
	// Sanity在Huffman期间启用其他运行时测试
	// 表结构。它的目的是在
	// 开发以补充当前的特殊单元测试。
	const sanity = false

	if h.min != 0 {
		*h = huffmanDecoder{}
	}

	// 计算每种长度的代码数，
	// 计算最小和最大长度。
	var count [maxCodeLen]int
	var min, max int
	for _, n := range lengths {
		if n == 0 {
			continue
		}
		if min == 0 || n < min {
			min = n
		}
		if n > max {
			max = n
		}
		count[n]++
	}

	// 空树。如果树发生故障，decompressor.huffSym函数稍后将失败
	// 使用。从技术上讲，空树仅对HDIST树和
	// 不是HCLEN和HLIT树。但是，具有空HCLEN树的流
	// 保证失败，因为它将尝试使用树来解码
	// HLIT和HDIST树的代码。类似地，空的HLIT树是
	// 保证稍后会失败，因为压缩数据部分必须
	// 由至少一个符号（块的结束标记）组成。
	if max == 0 {
		return true
	}

	code := 0
	var nextcode [maxCodeLen]int
	for i := min; i <= max; i++ {
		code <<= 1
		nextcode[i] = code
		code += count[i]
	}

	// 检查编码是否完整（即，我们已经
	// 已分配所有2到最大可能位序列）。
	// 例外：为了与zlib兼容，我们还需要
	// 接受退化的单代码编码。另见
	// 霍夫曼编码。
	if code != 1<<uint(max) && !(code == 1 && max == 1) {
		return false
	}

	h.min = min
	if max > huffmanChunkBits {
		numLinks := 1 << (uint(max) - huffmanChunkBits)
		h.linkMask = uint32(numLinks - 1)

		// 创建链接表
		link := nextcode[huffmanChunkBits+1] >> 1
		h.links = make([][]uint32, huffmanNumChunks-link)
		for j := uint(link); j < huffmanNumChunks; j++ {
			reverse := int(bits.Reverse16(uint16(j)))
			reverse >>= uint(16 - huffmanChunkBits)
			off := j - uint(link)
			if sanity && h.chunks[reverse] != 0 {
				panic("impossible: overwriting existing chunk")
			}
			h.chunks[reverse] = uint32(off<<huffmanValueShift | (huffmanChunkBits + 1))
			h.links[off] = make([]uint32, numLinks)
		}
	}

	for i, n := range lengths {
		if n == 0 {
			continue
		}
		code := nextcode[n]
		nextcode[n]++
		chunk := uint32(i<<huffmanValueShift | n)
		reverse := int(bits.Reverse16(uint16(code)))
		reverse >>= uint(16 - n)
		if n <= huffmanChunkBits {
			for off := reverse; off < len(h.chunks); off += 1 << uint(n) {
				// 我们永远不需要重写
				// 现有的块。而且，0是
				// 从来都不是有效的块，因为
				// 较低的4个“计数”位应为
				// 在1到15之间。
				if sanity && h.chunks[off] != 0 {
					panic("impossible: overwriting existing chunk")
				}
				h.chunks[off] = chunk
			}
		} else {
			j := reverse & (huffmanNumChunks - 1)
			if sanity && h.chunks[j]&huffmanCountMask != huffmanChunkBits+1 {
				// 应该使用更长的代码
				// 与上面的链接表关联。
				panic("impossible: not an indirect chunk")
			}
			value := h.chunks[j] >> huffmanValueShift
			linktab := h.links[value]
			reverse >>= huffmanChunkBits
			for off := reverse; off < len(linktab); off += 1 << uint(n-huffmanChunkBits) {
				if sanity && linktab[off] != 0 {
					panic("impossible: overwriting existing chunk")
				}
				linktab[off] = chunk
			}
		}
	}

	if sanity {
		// 在上面，我们已经检查了我们的头脑是否清醒，我们从未过度书写
		// 现有条目。在这里我们额外检查一下
		// 我们把桌子都坐满了。
		for i, chunk := range h.chunks {
			if chunk == 0 {
				// 作为一个例外，在
				// 单代码情况下，我们允许奇数
				// 要丢失的块。
				if code == 1 && i%2 == 1 {
					continue
				}
				panic("impossible: missing chunk")
			}
		}
		for _, linktab := range h.links {
			for _, chunk := range linktab {
				if chunk == 0 {
					panic("impossible: missing chunk")
				}
			}
		}
	}

	return true
}

// NewReader所需的实际读取接口。
// 如果传入的io.Reader没有ReadByte，
// NewReader将引入自己的缓冲。
type Reader interface {
	io.Reader
	io.ByteReader
}

// 解压状态。
type decompressor struct {
	// 输入源。
	r       Reader
	roffset int64

	// 输入位，在b的顶部。
	b  uint32
	nb uint

	// 用于文字/长度、距离的哈夫曼解码器。
	h1, h2 huffmanDecoder

	// 用于定义哈夫曼码的长度数组。
	bits     *[maxNumLit + maxNumDist]int
	codebits *[numCodes]int

	// 输出历史记录，缓冲区。
	dict dictDecoder

	// 临时缓冲区（避免重复分配）。
	buf [4]byte

	// 减压的下一步，
	// 减压状态。
	step      func(*decompressor)
	stepState int
	final     bool
	err       error
	toRead    []byte
	hl, hd    *huffmanDecoder
	copyLen   int
	copyDist  int
}

func (f *decompressor) nextBlock() {
	for f.nb < 1+2 {
		if f.err = f.moreBits(); f.err != nil {
			return
		}
	}
	f.final = f.b&1 == 1
	f.b >>= 1
	typ := f.b & 3
	f.b >>= 2
	f.nb -= 1 + 2
	switch typ {
	case 0:
		f.dataBlock()
	case 1:
		// 压缩，固定哈夫曼表
		f.hl = &fixedHuffmanDecoder
		f.hd = nil
		f.huffmanBlock()
	case 2:
		// 压缩的动态哈夫曼表
		if f.err = f.readHuffman(); f.err != nil {
			break
		}
		f.hl = &f.h1
		f.hd = &f.h2
		f.huffmanBlock()
	default:
		// 3号预订。
		f.err = CorruptInputError(f.roffset)
	}
}

func (f *decompressor) Read(b []byte) (int, error) {
	for {
		if len(f.toRead) > 0 {
			n := copy(b, f.toRead)
			f.toRead = f.toRead[n:]
			if len(f.toRead) == 0 {
				return n, f.err
			}
			return n, nil
		}
		if f.err != nil {
			return 0, f.err
		}
		f.step(f)
		if f.err != nil && len(f.toRead) == 0 {
			f.toRead = f.dict.readFlush() // 如果出现错误，请刷新剩余的内容
		}
	}
}

func (f *decompressor) Close() error {
	if f.err == io.EOF {
		return nil
	}
	return f.err
}

// RFC 1951第3.2.7节。
// 动态哈夫曼码的压缩

var codeOrder = [...]int{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}

func (f *decompressor) readHuffman() error {
	// HLIT[5]，HDIST[5]，HCLEN[4]。
	for f.nb < 5+5+4 {
		if err := f.moreBits(); err != nil {
			return err
		}
	}
	nlit := int(f.b&0x1F) + 257
	if nlit > maxNumLit {
		return CorruptInputError(f.roffset)
	}
	f.b >>= 5
	ndist := int(f.b&0x1F) + 1
	if ndist > maxNumDist {
		return CorruptInputError(f.roffset)
	}
	f.b >>= 5
	nclen := int(f.b&0xF) + 4
	// numCodes是19，所以nclen总是有效的。
	f.b >>= 4
	f.nb -= 5 + 5 + 4

	// （HCLEN+4）*3位：魔术码序中的代码长度。
	for i := 0; i < nclen; i++ {
		for f.nb < 3 {
			if err := f.moreBits(); err != nil {
				return err
			}
		}
		f.codebits[codeOrder[i]] = int(f.b & 0x7)
		f.b >>= 3
		f.nb -= 3
	}
	for i := nclen; i < len(codeOrder); i++ {
		f.codebits[codeOrder[i]] = 0
	}
	if !f.h1.init(f.codebits[0:]) {
		return CorruptInputError(f.roffset)
	}

	// HLIT+257码长，HDIST+1码长，
	// 使用代码长度的哈夫曼代码。
	for i, n := 0, nlit+ndist; i < n; {
		x, err := f.huffSym(&f.h1)
		if err != nil {
			return err
		}
		if x < 16 {
			// 实际长度。
			f.bits[i] = x
			i++
			continue
		}
		// 重复上一个长度或零。
		var rep int
		var nb uint
		var b int
		switch x {
		default:
			return InternalError("unexpected length code")
		case 16:
			rep = 3
			nb = 2
			if i == 0 {
				return CorruptInputError(f.roffset)
			}
			b = f.bits[i-1]
		case 17:
			rep = 3
			nb = 3
			b = 0
		case 18:
			rep = 11
			nb = 7
			b = 0
		}
		for f.nb < nb {
			if err := f.moreBits(); err != nil {
				return err
			}
		}
		rep += int(f.b & uint32(1<<nb-1))
		f.b >>= nb
		f.nb -= nb
		if i+rep > n {
			return CorruptInputError(f.roffset)
		}
		for j := 0; j < rep; j++ {
			f.bits[i] = b
			i++
		}
	}

	if !f.h1.init(f.bits[0:nlit]) || !f.h2.init(f.bits[nlit:nlit+ndist]) {
		return CorruptInputError(f.roffset)
	}

	// 作为优化，我们可以初始化一次读取的最小位
	// 因为我们知道，HLIT树的长度与EOB标记的长度相同
	// 每个块必须以一个终止。这保留了
	// 我们从不在DEFLATE流结束后读取任何额外的字节。
	if f.h1.min < f.bits[endBlockMarker] {
		f.h1.min = f.bits[endBlockMarker]
	}

	return nil
}

// 从f解码单个哈夫曼块。
// hl和hd是照明/长度值的哈夫曼状态
// 和距离值。如果hd==nil，则使用
// 与固定哈夫曼块关联的固定距离编码。
func (f *decompressor) huffmanBlock() {
	const (
		stateInit = iota // 零值必须是stateInit
		stateDict
	)

	switch f.stepState {
	case stateInit:
		goto readLiteral
	case stateDict:
		goto copyHistory
	}

readLiteral:
	// 根据RFC第3.2.3节读取文字和/或（长度、距离）。
	{
		v, err := f.huffSym(f.hl)
		if err != nil {
			f.err = err
			return
		}
		var n uint // 额外位数
		var length int
		switch {
		case v < 256:
			f.dict.writeByte(byte(v))
			if f.dict.availWrite() == 0 {
				f.toRead = f.dict.readFlush()
				f.step = (*decompressor).huffmanBlock
				f.stepState = stateInit
				return
			}
			goto readLiteral
		case v == 256:
			f.finishBlock()
			return
		// 否则，请参考较旧的数据
		case v < 265:
			length = v - (257 - 3)
			n = 0
		case v < 269:
			length = v*2 - (265*2 - 11)
			n = 1
		case v < 273:
			length = v*4 - (269*4 - 19)
			n = 2
		case v < 277:
			length = v*8 - (273*8 - 35)
			n = 3
		case v < 281:
			length = v*16 - (277*16 - 67)
			n = 4
		case v < 285:
			length = v*32 - (281*32 - 131)
			n = 5
		case v < maxNumLit:
			length = 258
			n = 0
		default:
			f.err = CorruptInputError(f.roffset)
			return
		}
		if n > 0 {
			for f.nb < n {
				if err = f.moreBits(); err != nil {
					f.err = err
					return
				}
			}
			length += int(f.b & uint32(1<<n-1))
			f.b >>= n
			f.nb -= n
		}

		var dist int
		if f.hd == nil {
			for f.nb < 5 {
				if err = f.moreBits(); err != nil {
					f.err = err
					return
				}
			}
			dist = int(bits.Reverse8(uint8(f.b & 0x1F << 3)))
			f.b >>= 5
			f.nb -= 5
		} else {
			if dist, err = f.huffSym(f.hd); err != nil {
				f.err = err
				return
			}
		}

		switch {
		case dist < 4:
			dist++
		case dist < maxNumDist:
			nb := uint(dist-2) >> 1
			// 在距离的底部有1位，需要更多nb。
			extra := (dist & 1) << nb
			for f.nb < nb {
				if err = f.moreBits(); err != nil {
					f.err = err
					return
				}
			}
			extra |= int(f.b & uint32(1<<nb-1))
			f.b >>= nb
			f.nb -= nb
			dist = 1<<(nb+1) + 1 + extra
		default:
			f.err = CorruptInputError(f.roffset)
			return
		}

		// 不检查长度；编码可以是有先见之明的。
		if dist > f.dict.histSize() {
			f.err = CorruptInputError(f.roffset)
			return
		}

		f.copyLen, f.copyDist = length, dist
		goto copyHistory
	}

copyHistory:
	// 根据RFC第3.2.3节进行反向复制。
	{
		cnt := f.dict.tryWriteCopy(f.copyDist, f.copyLen)
		if cnt == 0 {
			cnt = f.dict.writeCopy(f.copyDist, f.copyLen)
		}
		f.copyLen -= cnt

		if f.dict.availWrite() == 0 || f.copyLen > 0 {
			f.toRead = f.dict.readFlush()
			f.step = (*decompressor).huffmanBlock // 我们需要继续这项工作
			f.stepState = stateDict
			return
		}
		goto readLiteral
	}
}

// 将单个未压缩数据块从输入复制到输出。
func (f *decompressor) dataBlock() {
	// 未压缩。
	// 丢弃当前半字节。
	f.nb = 0
	f.b = 0

	// 然后是长度的一个补码。
	nr, err := io.ReadFull(f.r, f.buf[0:4])
	f.roffset += int64(nr)
	if err != nil {
		f.err = noEOF(err)
		return
	}
	n := int(f.buf[0]) | int(f.buf[1])<<8
	nn := int(f.buf[2]) | int(f.buf[3])<<8
	if uint16(nn) != uint16(^n) {
		f.err = CorruptInputError(f.roffset)
		return
	}

	if n == 0 {
		f.toRead = f.dict.readFlush()
		f.finishBlock()
		return
	}

	f.copyLen = n
	f.copyData()
}

// copyData将f.copyLen字节从基础读取器复制到f.hist。
// 当f.hist已满时，它暂停读取。
func (f *decompressor) copyData() {
	buf := f.dict.writeSlice()
	if len(buf) > f.copyLen {
		buf = buf[:f.copyLen]
	}

	cnt, err := io.ReadFull(f.r, buf)
	f.roffset += int64(cnt)
	f.copyLen -= cnt
	f.dict.writeMark(cnt)
	if err != nil {
		f.err = noEOF(err)
		return
	}

	if f.dict.availWrite() == 0 || f.copyLen > 0 {
		f.toRead = f.dict.readFlush()
		f.step = (*decompressor).copyData
		return
	}
	f.finishBlock()
}

func (f *decompressor) finishBlock() {
	if f.final {
		if f.dict.availRead() > 0 {
			f.toRead = f.dict.readFlush()
		}
		f.err = io.EOF
	}
	f.step = (*decompressor).nextBlock
}

// noEOF返回err，除非err==io.EOF，在这种情况下，它返回io.errunexpectedof。
func noEOF(e error) error {
	if e == io.EOF {
		return io.ErrUnexpectedEOF
	}
	return e
}

func (f *decompressor) moreBits() error {
	c, err := f.r.ReadByte()
	if err != nil {
		return noEOF(err)
	}
	f.roffset++
	f.b |= uint32(c) << f.nb
	f.nb += 8
	return nil
}

// 根据h从f中读取下一个哈夫曼编码符号。
func (f *decompressor) huffSym(h *huffmanDecoder) (int, error) {
	// 因为huffmanDecoder可以是空的，也可以由退化树组成
	// 对于单个元素，huffSym必须在这两个边缘情况下出错。两者
	// 在某些情况下，无效序列的chunks切片将为0，并将其前导
	// 满足下面的n==0检查。
	n := uint(h.min)
	// 优化。编译器不够聪明，无法将f.b、f.nb保存在寄存器中，
	// 但它足够聪明，可以在寄存器中保留局部变量，所以使用nb和b，
	// 内联调用moreBits并在返回时将b、nb重新分配回f。
	nb, b := f.nb, f.b
	for {
		for nb < n {
			c, err := f.r.ReadByte()
			if err != nil {
				f.b = b
				f.nb = nb
				return 0, noEOF(err)
			}
			f.roffset++
			b |= uint32(c) << (nb & 31)
			nb += 8
		}
		chunk := h.chunks[b&(huffmanNumChunks-1)]
		n = uint(chunk & huffmanCountMask)
		if n > huffmanChunkBits {
			chunk = h.links[chunk>>huffmanValueShift][(b>>huffmanChunkBits)&h.linkMask]
			n = uint(chunk & huffmanCountMask)
		}
		if n <= nb {
			if n == 0 {
				f.b = b
				f.nb = nb
				f.err = CorruptInputError(f.roffset)
				return 0, f.err
			}
			f.b = b >> (n & 31)
			f.nb = nb - n
			return int(chunk >> huffmanValueShift), nil
		}
	}
}

func makeReader(r io.Reader) Reader {
	if rr, ok := r.(Reader); ok {
		return rr
	}
	return bufio.NewReader(r)
}

func fixedHuffmanDecoderInit() {
	fixedOnce.Do(func() {
		// 这些来自RFC第3.2.6节。
		var bits [288]int
		for i := 0; i < 144; i++ {
			bits[i] = 8
		}
		for i := 144; i < 256; i++ {
			bits[i] = 9
		}
		for i := 256; i < 280; i++ {
			bits[i] = 7
		}
		for i := 280; i < 288; i++ {
			bits[i] = 8
		}
		fixedHuffmanDecoder.init(bits[:])
	})
}

func (f *decompressor) Reset(r io.Reader, dict []byte) error {
	*f = decompressor{
		r:        makeReader(r),
		bits:     f.bits,
		codebits: f.codebits,
		dict:     f.dict,
		step:     (*decompressor).nextBlock,
	}
	f.dict.init(maxMatchOffset, dict)
	return nil
}

// NewReader返回可使用的新ReadCloser
// 读取r的未压缩版本。
// 如果r也不实现io.ByteReader，
// 解压器可以从r读取比需要更多的数据。
// 呼叫人有责任在ReadCloser上呼叫Close
// 读完后。
// None
// NewReader返回的ReadCloser还实现了重置。
func NewReader(r io.Reader) io.ReadCloser {
	fixedHuffmanDecoderInit()

	var f decompressor
	f.r = makeReader(r)
	f.bits = new([maxNumLit + maxNumDist]int)
	f.codebits = new([numCodes]int)
	f.step = (*decompressor).nextBlock
	f.dict.init(maxMatchOffset, nil)
	return &f
}

// NewReaderDict与NewReader类似，但会初始化读取器
// 使用预设词典。返回的读取器的行为就像
// 未压缩的数据流从给定的字典开始，
// 已经读过了。通常使用NewReaderDict
// 读取由NewWriterDict压缩的数据。
// None
// NewReader返回的ReadCloser还实现了重置。
func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser {
	fixedHuffmanDecoderInit()

	var f decompressor
	f.r = makeReader(r)
	f.bits = new([maxNumLit + maxNumDist]int)
	f.codebits = new([numCodes]int)
	f.step = (*decompressor).nextBlock
	f.dict.init(maxMatchOffset, dict)
	return &f
}
